/*
Source : https://leetcode.com/problems/longest-valid-parentheses/
Author : nflush@outlook.com
Date   : 2016-05-05
*/
/*
32. Longest Valid Parentheses

    Total Accepted: 71853
    Total Submissions: 315388
    Difficulty: Hard

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Subscribe to see which companies asked this question
*/
/* 错误解法 */
class Solution {
public:
    int longestValidParentheses(string s) {
        int size = s.size();
        int len = 0;
        int maxLen = 0;
        int saveLen = 0;
        int ll = 0;
        int rr = 0;
        for (int i = 0; i < size; i++) {
            if (s[i] == '(') {
                ll++;
                len++;
                rr = 0;
            } else {
                if (ll){
                    ll--;
                    len++;
                    rr++;
                    if (ll == 0){
                        saveLen += len;
                        len = 0;
                        if (saveLen > maxLen){
                            maxLen = saveLen;
                        }
                    } else {
                        int tmp = 2 * rr;
                        if (tmp > maxLen){
                            maxLen = tmp;
                        }
                    }
                } else {
                    rr = 0;
                    saveLen = 0;
                    if (maxLen + i > size) break;
                }
            }
        }
        // if (len - ll > maxLen) maxLen = len - ll;
        return maxLen;
    }
};

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
        int lastError = -1;
        vector<int> stack;
        int size = s.size();

        for(int i=0; i<size; i++){
            if (s[i] == '('){
                stack.push_back(i);
            }else if (s[i] == ')') {
                if (stack.size()>0 ){
                    stack.pop_back();
                    int len;
                    if (stack.size()==0){
                        len = i - lastError;
                    } else {
                        len = i - stack.back();
                    }
                    if (len > maxLen) {
                        maxLen = len;
                    }
                }else{
                    lastError = i;
                    if (maxLen + i > size) break;
                }
            }
        }
        return maxLen;
    }
};